代码之家 › 专栏 › 技术社区 › Jagannath

在二进制搜索树中连接兄弟姐妹

Jagannath · 技术社区 · 16 年前

我正在尝试连接二进制搜索树的兄弟姐妹。您可以在connect()方法中找到逻辑。我的问题是,还有更好的方法吗?使用两个队列来实现逻辑是否过度?

using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text;

namespace SampleCSParallel
{
    class Tree
    {
        public Tree left = null;
        public Tree right = null;
        public Tree sibling = null;
        public int _data;

        Tree(int data)
        {
            _data = data;
            left = null;
            right = null;
        }

        public Tree Left
        {
            get
            {
                return this.left;
            }
        }

        public Tree Right
        {
            get
            {
                return this.right;
            }
        }

        public Tree AddNode(Tree node, int data)
        {
            if (node == null)
            {
                node = new Tree(data);
                return node;
            }
            else if (node._data <= data)
            {
                node.left = AddNode(node.left, data);
            }
            else if (node._data > data)
            {
                node.right = AddNode(node.right, data);
            }
            return node;
        }

        public static Tree CreateTree(Tree node, int depth, int start)
        {
            if (node == null)
                node = new Tree(start);
            if (depth > 1)
            {
                node.left = CreateTree(node.left, depth - 1, start + 1);
                node.right = CreateTree(node.right, depth - 1, start + 1);
            }
            return node;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            //Tree node = null;
            Tree tr = Tree.CreateTree(null, 4, 1);
            Stopwatch sw = Stopwatch.StartNew();
            int total = WalkTree(tr);           
            TimeSpan ts = sw.Elapsed;
            Console.WriteLine("in {0} sec", ts.Seconds);
            Console.WriteLine("total:{0}", total);
            connect(tr);
            Console.ReadLine();
        }        

        static void connect(Tree root)
        {
            Queue<Tree> nodeQueue = new Queue<Tree>();          
            nodeQueue.Enqueue(root);
            Console.WriteLine(root._data);
            connectSiblings(nodeQueue);
        }

        static void connectSiblings(Queue<Tree> nodeQueue)
        {
            Queue<Tree> childrenQueue = new Queue<Tree>();            
            StringBuilder MsgStr = new StringBuilder();
            bool done = false;

             while (!done)
             {
                while (nodeQueue.Count != 0)
                {

                    Tree parent = nodeQueue.Dequeue();                  
                    if (parent.left != null)
                    {
                        childrenQueue.Enqueue(parent.left);
                    }
                    if (parent.right != null)
                    {
                        childrenQueue.Enqueue(parent.right);
                    }           
                }

                 Tree prevNode = null;
                 Tree currNode = null;
                while (childrenQueue.Count != 0)
                {
                    currNode = childrenQueue.Dequeue();
                    nodeQueue.Enqueue(currNode);                

                    if (prevNode != null)
                    {                       
                        MsgStr.Append(string.Format("\t{0}",currNode._data));                   
                    }
                    else
                    {
                        prevNode = currNode;                        
                        MsgStr.Append(string.Format("\t{0}",prevNode._data));
                    }           
                }                   
                Console.WriteLine(MsgStr.ToString());
                MsgStr.Remove(0, MsgStr.Length);

                if (nodeQueue.Count == 0 && childrenQueue.Count == 0)
                    done = true;
             }
        }
    }  
}

2 回复 | 直到 13 年前

Martin v. Löwis 16 年前

可以使用prev节点数组以递归方式连接兄弟节点,每个深度一个:

void connect(Node node, int depth, List<Node> prev)
{
  if (node == null)
    return;
  if(prev.Size <= depth)
    prev.Add(depth);
  else {
    prev[depth].sibling = node;
    prev[depth] = node;
  }
  connect(node.left, depth+1, prev);
  connect(node.right, depth+1, prev);
}

Anupam Gupta 13 年前

我尝试用Java中O(1)的空间复杂度来解决这个问题。

public void setSibling(Node root){
        Node start = null;
        if (root == null) return;
        do{
            if(root.left!=null) {
                root.left.sibling = getNextSibling(root,"left");
                if(start == null) start = root.left;
            }
            if(root.right!=null){
                root.right.sibling = getNextSibling(root,"right");
                if(start == null) start = root.right;
            }
            root = root.sibling;
        }while(root!=null);
        root = start;
        setSibling(root);

    }


    public Node getNextSibling(Node root,String marker){
        if (marker.equals("left")){
            if(root.right!=null)return root.right;
        }
        Node nextSibling = null;
        root = root.sibling;
        while(nextSibling == null && root != null){
            if (root.left != null) nextSibling = root.left;
            else if (root.right != null) nextSibling = root.right;
            else root = root.sibling;
        }
        return nextSibling;
    }

它可能不优雅,但它起作用。